package club.worldbang.structures.stack;

import java.io.Serializable;
import java.util.EmptyStackException;
//数组实现栈
public class SeqStack<T> implements Stack<T>, Serializable {
	private static final long serialVersionUID = -2100811647283606968L;
	/**
	 * 栈顶指针,-1代表空栈
	 */
	private int top = -1;

	/**
	 * 容量大小默认为10
	 */
	private int capacity = 10;

	/**
	 * 存放元素的数组
	 */
	private T[] array;

	private int size;

	public SeqStack(int capacity) {
		array = (T[]) new Object[capacity];
	}

	public SeqStack() {
		new SeqStack<>(this.capacity);
	}

	@Override
	public boolean isEmpty() {
		return this.top == -1;// 空栈标识
	}

	// 入栈，从栈顶添加（即数组尾部）
	@Override
	public void push(T data) {
		// 判断容量
		if (array.length == size) {
			// 扩容
			ensureCapacity(size * 2 + 1);
		}
		// 从栈顶添加元素
		array[++top] = data;
		size++;
	}

	// 扩容
	private void ensureCapacity(int capacity) {
		if (capacity < size) {
			return;
		}
		T[] old = array;
		array = (T[]) new Object[capacity];
		for (int i = 0; i < old.length; i++) {
			array[i] = old[i];
		}
	}

	// 获取栈顶元素，不出栈
	@Override
	public T peek() {
		if (isEmpty()) {
			throw new EmptyStackException();
		}
		return array[top];
	}

	// 出栈
	@Override
	public T pop() {
		if (isEmpty()) {
			throw new EmptyStackException();
		}
		size--;

		return array[top--];
	}

}
